package cn.zifangsky.sort;

/**
 * 插入法排序
 *
 * @author zifangsky
 * @date 2019/1/3
 * @since 1.0.0
 */
public class InsertionSort {

    /**
     * 插入法排序
     * <p><b>时间复杂度：</b>O(n^2)</p>
     * @author zifangsky
     * @date 2019/1/3 11:13
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sort(int[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;
        for(int i = 1; i < length; i++){
            int temp = array[i];

            int j;
            for(j = (i - 1); j >= 0 && temp < array[j]; j--) {
                //如果temp < array[j]，则array[j]向右移动一位
                array[j + 1] = array[j];
            }
            //将temp放到正确位置
            array[j + 1] = temp;
        }

        return array;
    }

}
